package Comprehensive_02;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 快排3.0:
 * 随机从数组中取一个数为基准值,比基准值大的排右边,比基准值小的排左边
 */
public class QuickSort_3 {
    public static void main(String[] args) {
        int[] arr = {3, 1, 3, 2, 6, 5, 3, 4};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr) {
        quickSortInternal(arr,0, arr.length - 1);
    }


    private static void quickSortInternal(int[] arr, int l, int r) {
        if (l > r){
            return;
        }

        int p = partition(arr, l, r);
        quickSortInternal(arr, l,  p - 1);
        quickSortInternal(arr, p + 1, r);
    }

    private static int partition(int[] arr, int l, int r) {
        ThreadLocalRandom random=ThreadLocalRandom.current();
        int randomIndex = random.nextInt(l,r + 1);
        swap(arr,l,randomIndex);
        int base = arr[l];
        int m = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < base) {
                swap(arr, m++ + 1, i);
            }
        }
        swap(arr, l , m);
        return m;
    }

    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
